package leetcode.biweekly.week96;

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.TreeMap;

//Solution3Test
public class Solution6 {
	public long maxScore(int[] nums1, int[] nums2, int k) {
		int n = nums1.length;
		int[][] nums = new int[n][2];
		for (int i = 0; i < n; i++) {
			nums[i][0] = nums1[i];// add
			nums[i][1] = nums2[i];// mul
		}
//		Arrays.sort(nums, (a, b) -> a[1] == b[1] ? b[0] - a[0] : b[1] - a[1]);

		long sum = 0;
		PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> a[0] - b[0]);
		TreeMap<Integer, Integer> tm = new TreeMap<>();
		int p = 0;
		while (p < k) {
			int[] cur = nums[p];
			int add = cur[0], mult = cur[1];
			sum += 1l * add;
			queue.add(new int[] { add, mult });
			tm.put(mult, tm.getOrDefault(mult, 0) + 1);
			p++;
		}
		long ans = 1l * sum * tm.firstKey();
		while (p < n) {
			int[] cur = nums[p];
			int add = cur[0], mult = cur[1];
			if (!queue.isEmpty() && add > queue.peek()[0]) {
				int[] poll = queue.poll();
				sum = sum - poll[0] + add;
				int rest = tm.get(poll[1]);
				if (rest == 1) {
					tm.remove(poll[1]);
				} else {
					tm.put(poll[1], rest - 1);
				}
				tm.put(mult, tm.getOrDefault(mult, 0) + 1);
				queue.add(new int[] { add, mult });
				ans = Math.max(ans, 1l * sum * tm.firstKey());
			}
			p++;
		}
		return ans;
	}

}
